package me.mingshan.leetcode;

import java.util.*;

/**
 * https://leetcode.cn/problems/binary-tree-right-side-view/description/
 *
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 *
 * @author hanjuntao
 * @date 2025/8/29 0029
 */
public class L_199_二叉树的右视图 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        //       1
        //      2  3
        //    4   5

        System.out.println(rightSideView(root));  // [1, 2, 4, 5, 3]
    }


    /**
     * 从题意可知，可以采用层序遍历(使用队列，当前层遍历时，将左右子节点依次放入队列中)
     * 每一层只返回最右边的节点
     *
     *
     * @param root
     * @return
     */
    public static List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

        List<Integer> result = new ArrayList<>();

        // 层序遍历逻辑：
        // 当遍历当前层时，将当前层的左右节点加入队列
        // 如何知道有没有遍历完当前层呢？

        // 层数
        int level = 0;
        // 当前层节点总数
        int curLevelNodesTotal = 0;
        // 当前层遍历的节点个数
        int cntNode = 0;

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        level++;
        curLevelNodesTotal++;

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
            cntNode++;

            // 当前层遍历结束
            if (cntNode == curLevelNodesTotal) {
                result.add(node.val);
                level++;
                curLevelNodesTotal = queue.size();
                cntNode = 0;
            }
        }

        return result;
    }


}
